Search for: All records

Modern Datalog engines (e.g., LogicBlox, Soufflé, ddlog) enable their users to write declarative queries which com- pute recursive deductions over extensional facts, leaving high-performance operationalization (query planning, semi- naïve evaluation, and parallelization) to the engine. Such engines form the backbone of modern high-throughput ap- plications in static analysis, network monitoring, and social- media mining. In this paper, we present a methodology for implementing a modern in-memory Datalog engine on data center GPUs, allowing us to achieve significant (up to 45×) gains compared to Soufflé (a modern CPU-based en- gine) on context-sensitive points-to analysis of PostgreSQL. We present GPUlog, a Datalog engine backend that imple- ments iterated relational algebra kernels over a novel range- indexed data structure we call the hash-indexed sorted ar- ray (HISA). HISA combines the algorithmic benefits of in- cremental range-indexed relations with the raw computa- tion throughput of operations over dense data structures. Our experiments show that GPUlog is significantly faster than CPU-based Datalog engines while achieving a favorable memory footprint compared to contemporary GPU-based joins.